// Copyright (c) 2010, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// ---
// Author: Jeffrey Junfeng Pan (panjunfeng@gmail.com)

#ifndef FP_GROWTH_DICTIONARY_H_
#define FP_GROWTH_DICTIONARY_H_

// ItemDictionary is used for scanning through all items in the given itemsets.
// It extracts all the unique items, count their frequency and sort all items
// based on their frequencies descendingly. It gives each item an index. Items
// with higher frequencies have smaller indices. ItemDictionary builds all the
// indices, find index for a given item and find item for a given index.

#include <algorithm>
#include <unordered_map>
#include <sstream>
#include <string>
#include <vector>

#include "base.h"
#include "common/logging.h"
#include "common/scoped_ptr.h"
#include "transactions.h"


// Whether the algorithm tries to keep the original item order of
// mined patterns. For example, if 'new' more likely to appear
// before 'york', The mined patterns will keep items in this order:
// 'new york' rather than 'york new'. It needs O(N^2) memory to
// store the partial order of items where N is the number of unique
// items in all transactions. The partial order graph is stored in a
// spare matrix. Thus, it actually needs less memory than O(N^2).
#define FLAGS_keep_item_order false

namespace std { using namespace __gnu_cxx; }
using namespace std;

/** BEGIN FIX **/
//namespace __gnu_cxx {
//template<> struct hash< std::string > {
//  size_t operator()( const std::string& x ) const {
//    return hash< const char* >()( x.c_str() );
//  }
//};
//}
/** END FIX **/

namespace frequent_pattern_mining {

// ------------------------------------------------------------
//                      Declaration
// ------------------------------------------------------------

template <typename T>
class ItemDictionary {
 public:
  typedef ItemFrequencyPair<int> IndexFrequencyPair;

  // mapping from item to index and freqeuency pair
  typedef unordered_map<T, IndexFrequencyPair> ItemHashMap;

  // mapping from a given index to its item and frequency pair
  typedef vector<ItemFrequencyPair<T> > IndexVector;

  // store the partial order of item indices in the original transactions.
  typedef vector<unordered_map<int, int> > IndexOrder;

  // constructor: build an empty dictionary
  explicit ItemDictionary(T impossible_item);

  // Build the Item Dictionary using either min_support_count or
  // min_support_ratio. Only one min_support shall be properly set.
  // The other is set to any negative value. For example:
  // 1) Set by min_support_count = 10
  //    BuildDictionary(transaction, 10, -1)
  // 2) Set by min_support_ratio = 0.5
  //    BuildDictionary(transaction, -1, 0.5);
  void BuildDictionary(Transactions<T>* transactions,
                       int min_support_count,
                       double min_support_ratio);

  // Convert the itemset into their index itemset.
  // All item indices are kept in their original order in the transaction.
  // Items with frequency less than min_support_count are discarded.
  // Duplicated items are not removed.
  void ConvertTransactionToRawIndices(const vector<T>& transaction,
                                      vector<int>* indices);

  // Convert the itemset into their index itemset.
  // All items are sorted by their frequency in descending order.
  // Items with frequency less than min_support_count are discarded.
  // Duplicated items are removed.
  void ConvertTransactionToSortedIndices(const vector<T>& transaction,
                                         vector<int>* indices);

  // Sort all items in a transaction so that they approximately
  // follow the order they appear in the original transactions.
  void SortItemsByPartialOrder(vector<T>* items);

  // Sort all items in a transaction so that they approximately
  // follow the order they appear in the original transactions.
  void SortIndicesByPartialOrder(vector<int>* indices);

  // get index given the item
  int GetIndexForItem(const T& item);

  // get item given the index
  T GetItemForIndex(int index);

  string GetItemTextForIndex(int index);

  // get frequency given the item
  int GetFrequencyForItem(const T& item);

  // get frequency given the index
  int GetFrequencyForIndex(int index);

  // output the dictionary
  string ToString() const;

  // retrieve the item to <index, frequency> pair mapping
  const ItemHashMap& item_map() const;

  // retrieve the index to <item, frequency> pair mapping
  const IndexVector& index_vector() const;

  // retrieve the index partial order mapping
  const IndexOrder& index_order() const;

  // total number of transactions via counting each transaction's frequency.
  int num_transactions() const;

  // retrieve the minimal support count
  int min_support_count() const;

  // retrieve the minimal support ratio
  double min_support_ratio() const;

  // non-existant index
  static const int IMPOSSIBLE_INDEX = -1;

 private:

  // insert an itemset into the dictionary
  void InsertItemset(const vector<T>& transaction, int frequency);

  // store the hash mapping from item to <item index, frequency> pair
  scoped_ptr<ItemHashMap> item_map_;

  // store the mapping from index to <item, frequency> pair
  scoped_ptr<IndexVector> index_vector_;

  // store statistically the partial order of item indices in the original
  // transactions. for example there are two transactions:
  //   1) A B C
  //   2) E B C
  // we know A < B < C according to their order from 1) and E < B < C from 2)
  // but we can't compare A & E since no information is available. from the
  // value stored, we have:
  //   1) index_order_[i][j] < 0 means item i statistically appears ahead of j.
  //   2) index_order_[i][j] > 0 means item i statistically appears after j.
  //   3) index_order_[i][j] = 0 means item i and j have equal chance appear
  //      ahead of each oter.
  //   4) index_order_[i][j] having missing value means the order is unknown.
  //
  //  ####################### WARNING ######################
  //  There might be a loop in the partial order graph,
  //  for example, if the transactions are:
  //    1) A B C
  //    2) B C A
  //    3) C A B
  //  And we want to sort A B C, in which there is a loop.
  //  In such case, the sorting result can be 1) or 2) or 3).
  scoped_ptr<IndexOrder> index_order_;

  // total number of transactions via counting each transaction's frequency.
  int num_transactions_;

  // Minimal support for frequent pattern mining.
  // The range is in [0, transactions_.size()]
  // min_support_count_ = ceil(min_support_ratio_ * transactions_.size())
  int min_support_count_;

  // impossible item value
  const T impossible_item_;

  DISALLOW_EVIL_CONSTRUCTORS(ItemDictionary);
};

// ------------------------------------------------------------
//                      Definition
// ------------------------------------------------------------

// sort items based on their statistical order from all transactions.
// if left_item appears ahead of right_item more often than the reverse
// order, return true. otherwise return false.
template <typename T>
class ItemCompareByPartialOrder {
 public:
  explicit ItemCompareByPartialOrder(ItemDictionary<T>* parent)
    : parent_(parent) {
  }

  bool operator() (const T& left_item, const T& right_item) {
    int left_index = parent_->GetIndexForItem(left_item);
    int right_index = parent_->GetIndexForItem(right_item);
    unordered_map<int, int>::const_iterator iter =
      parent_->index_order()[left_index].find(right_index);
    if (iter != parent_->index_order()[left_index].end()) {
      return iter->second < 0;
    } else {
      return false;
    }
  }

 private:
  ItemDictionary<T>* parent_;  // Not owned.
};

// sort items based on their statistical order from all transactions.
// if left_item appears ahead of right_item more often than the reverse
// order, return true. otherwise return false.
template <typename T>
class IndexCompareByPartialOrder {
 public:
  explicit IndexCompareByPartialOrder(ItemDictionary<T>* parent)
    : parent_(parent) {
  }

  bool operator() (const int& left_index, const int& right_index) {
    unordered_map<int, int>::const_iterator iter =
      parent_->index_order()[left_index].find(right_index);
    if (iter != parent_->index_order()[left_index].end()) {
      return iter->second < 0;
    } else {
      return false;
    }
  }

 private:
  ItemDictionary<T>* parent_;  // Not owned.
};

// sort items based on their frequency descendingly.
template <typename T>
class ReverseItemFrequencyPairCompare {
 public:
  int operator() (const ItemFrequencyPair<T>&  left,
                  const ItemFrequencyPair<T>& right) {
    return left.frequency > right.frequency;
  }
};

// constructor: build an empty dictionary
template <typename T>
ItemDictionary<T>::ItemDictionary(T impossible_item)
  : item_map_(new ItemHashMap),
    index_vector_(new IndexVector),
    index_order_(new IndexOrder),
    num_transactions_(0),
    min_support_count_(0),
    impossible_item_(impossible_item) {
}

// insert an itemset into the dictionary
template <typename T>
void ItemDictionary<T>::InsertItemset(const vector<T>& transaction,
                                      int frequency) {
  for (int j = 0; j < transaction.size(); ++j) {
    typename ItemHashMap::iterator iter =
      item_map_->find(transaction[j]);
    if (iter == item_map_->end()) {
      // the index is set to IMPOSSIBLE_INDEX initially since it is unknown.
      IndexFrequencyPair value;
      value.value = IMPOSSIBLE_INDEX;
      value.frequency = frequency;
      item_map_->insert(pair<T, IndexFrequencyPair>(transaction[j],
                                                    value));
    } else {
      iter->second.frequency += frequency;
    }
  }
}

// Build the Item Dictionary using either min_support_count or
// min_support_ratio. Only one min_support shall be properly set.
// The other is set to any negative value. For example:
// 1) Set by min_support_count = 10
//    BuildDictionary(transaction, 10, -1)
// 2) Set by min_support_ratio = 0.5
//    BuildDictionary(transaction, -1, 0.5);
template <typename T>
void ItemDictionary<T>::BuildDictionary(Transactions<T>* transactions,
                                        int min_support_count,
                                        double min_support_ratio) {
  // There shall be only one valid min_support.
  CHECK_EQ(true, (min_support_count < 0 && min_support_ratio >= 0) ||
                 (min_support_count >= 0 && min_support_ratio < 0));

  // Initialize all mappings
  item_map_.reset(new ItemHashMap);
  index_vector_.reset(new IndexVector);
  num_transactions_ = 0;
  // Build the item to <index, frequency> mapping. The index is filled
  // with a default value (IMPOSSIBLE_INDEX) at this stage since the
  // value is unknown yet.
  for (int i = 0; transactions->is_valid(i); ++i) {
    InsertItemset((*transactions)[i], (*transactions)(i));
    num_transactions_ += (*transactions)(i);
  }

  // Configurate min_support_count_
  min_support_count_ = min_support_count >= 0 ? min_support_count :
    GetCountFromRatio(num_transactions_, min_support_ratio);
  LOG_IF(WARNING, min_support_count_ > num_transactions_)
    << "min_support_count shall be <= num_transactions. But it doesnt hurt.";

  // Build the index to <item, frequency> mapping
  for (typename ItemHashMap::const_iterator i = item_map_->begin();
       i != item_map_->end();
       ++i) {
    ItemFrequencyPair<T> value;
    value.value = i->first;
    value.frequency = i->second.frequency;
    index_vector_->push_back(value);
  }

  // Sanity Check: whether the impossible_item_ exists in transactions.
  for (int i = 0; i < index_vector_->size(); ++i) {
    CHECK_NE((*index_vector_)[i].value, impossible_item_)
      << ": impossible_item exists in transactions!!!";
  }

  // Sort and find the elements which frequency are less than min support count.
  sort(index_vector_->begin(),
       index_vector_->end(),
       ReverseItemFrequencyPairCompare<T>());
  int position = index_vector_->size();
  for (int i = 0; i < index_vector_->size(); ++i) {
    if ((*index_vector_)[i].frequency < min_support_count_) {
      position = i;
      break;
    }
  }

  // Set the index in the item to <index, frequency> mapping
  for (int i = 0; i < index_vector_->size(); ++i) {
    if (i < position) {
      // the item has a frequency >= min_support_count_, keep it.
      (*item_map_)[(*index_vector_)[i].value].value = i;
    } else {
      // the item has a frequency < min_support_count_, delete it.
      item_map_->erase((*index_vector_)[i].value);
    }
  }  // for int i
  // The items with the frequency less than the min support are discarded.
  index_vector_->resize(position);

  // Create the partial order sparse matrix for possible item indices.
  index_order_.reset(new IndexOrder);
  index_order_->resize(position);
  if (FLAGS_keep_item_order) {
    for (int i = 0; transactions->is_valid(i); ++i) {
      vector<int> indices;
      ConvertTransactionToRawIndices((*transactions)[i], &indices);
      for (int j = 0; j < indices.size(); ++j) {
        for (int k = j + 1; k < indices.size(); ++k) {
          if ((*index_order_)[indices[j]].find(indices[k]) !=
              (*index_order_)[indices[j]].end()) {
            (*index_order_)[indices[j]][indices[k]] += -1;
            (*index_order_)[indices[k]][indices[j]] += 1;
          } else {
            (*index_order_)[indices[j]][indices[k]] = -1;
            (*index_order_)[indices[k]][indices[j]] = 1;
          }  // if found
        }  // for k
      }  // for j
    }  // for i
  }  // if FLAGS
}

// Convert the itemset into their index itemset.
// All item indices are kept in their original order in the transaction.
// Items with frequency less than min_support_count are discarded.
// Duplicated items are not removed.
template <typename T>
void ItemDictionary<T>::ConvertTransactionToRawIndices(
    const vector<T>& transaction,
    vector<int>* indices) {
  CHECK(indices) << ": indices must not be NULL";
  indices->clear();
  for (int j = 0; j < transaction.size(); ++j) {
    int index = GetIndexForItem(transaction[j]);
    if (index != IMPOSSIBLE_INDEX) {
      indices->push_back(index);
    }
  }
}

// Convert the itemset into their index itemset.
// All items are sorted by their frequency in descending order.
// Items with frequency less than min_support_count are discarded.
// Duplicated items are removed.
template <typename T>
void ItemDictionary<T>::ConvertTransactionToSortedIndices(
    const vector<T>& transaction,
    vector<int>* indices) {
  CHECK(indices) << ": indices must not be NULL";
  indices->clear();
  for (int j = 0; j < transaction.size(); ++j) {
    int index = GetIndexForItem(transaction[j]);
    if (index != IMPOSSIBLE_INDEX) {
      indices->push_back(index);
    }
  }
  sort(indices->begin(), indices->end());
  // remove duplicated indices
  if (indices->size() > 0) {
    for (int j = 0; j < indices->size() - 1; ++j) {
      if ((*indices)[j] == (*indices)[j + 1]) {
        LOG(INFO) << ": remove duplicate item "
                  << GetItemForIndex((*indices)[j + 1]);
        indices->erase(indices->begin() + j + 1);
      }
    }
  }
}


// Sort all items in a transaction so that they approximately
// follow the order they appear in the original transactions.
template <typename T>
void ItemDictionary<T>::SortItemsByPartialOrder(vector<T>* items) {
  CHECK(items) << ": items (transaction) can not be NULL";
  if (FLAGS_keep_item_order) {
    sort(items->begin(), items->end(), ItemCompareByPartialOrder<T>(this));
  }
}

// Sort all items in a transaction so that they approximately
// follow the order they appear in the original transactions.
template <typename T>
void ItemDictionary<T>::SortIndicesByPartialOrder(vector<int>* indices) {
  CHECK(indices) << ": indices (transaction) can not be NULL";
  if (FLAGS_keep_item_order) {
    sort(indices->begin(), indices->end(), IndexCompareByPartialOrder<T>(this));
  }
}

// get index given the item
template <typename T>
int ItemDictionary<T>::GetIndexForItem(const T& item) {
  typename ItemHashMap::const_iterator iter =
    item_map_->find(item);
  if (iter != item_map_->end()) {
    return iter->second.value;
  } else {
    return IMPOSSIBLE_INDEX;
  }
}

// get frequency given the item
template <typename T>
int ItemDictionary<T>::GetFrequencyForItem(const T& item) {
  typename ItemHashMap::const_iterator iter =
    item_map_->find(item);
  if (iter != item_map_->end()) {
    return iter->second.frequency;
  } else {
    return 0;
  }
}

// get item given the index
template <typename T>
T ItemDictionary<T>::GetItemForIndex(int index) {
  if (index < 0 || index >= index_vector_->size()) {
    return impossible_item_;
  } else {
    return (*index_vector_)[index].value;
  }
}

// get item (string) given the index
template <typename T>
string ItemDictionary<T>::GetItemTextForIndex(int index) {
  return ItemToString(GetItemForIndex(index));
}

// get frequency given the index
template <typename T>
int ItemDictionary<T>::GetFrequencyForIndex(int index) {
  if (index < 0 || index >= index_vector_->size()) {
    return 0;
  } else {
    return (*index_vector_)[index].frequency;
  }
}

// retrieve the item to <index, frequency> pair mapping
template <typename T>
const typename ItemDictionary<T>::ItemHashMap&
ItemDictionary<T>::item_map() const {
  return (*item_map_);
}

// retrieve the index to <item, frequency> pair mapping
template <typename T>
const typename ItemDictionary<T>::IndexVector&
ItemDictionary<T>::index_vector() const {
  return (*index_vector_);
}

// retrieve the index partial order
template <typename T>
const typename ItemDictionary<T>::IndexOrder&
ItemDictionary<T>::index_order() const {
  return (*index_order_);
}

// retrieve the number of transactions processed
template <typename T>
int ItemDictionary<T>::num_transactions() const {
  return num_transactions_;
}

// retrieve the minimal support count
template <typename T>
int ItemDictionary<T>::min_support_count() const {
  return min_support_count_;
}

// retrieve the minimal support ratio
template <typename T>
double ItemDictionary<T>::min_support_ratio() const {
  return GetRatioFromCount(num_transactions_, min_support_count_);
}

// output the dictionary
template <typename T>
string ItemDictionary<T>::ToString() const {
  ostringstream oss;

  oss << "-----------------------------------------------------------\n";
  oss << "Number of Transactions: " << num_transactions_ << endl;
  oss << "Number of Unique Items: " << index_vector_->size() << endl;
  oss << "------- Mapping from Index to <Item, Frequency> Pair ------\n";
  for (int i = 0; i < index_vector_->size(); ++i) {
    oss << "INDEX " << i << " FREQUENCY "
        << (*index_vector_)[i].frequency
        << " ITEM " << (*index_vector_)[i].value
        << endl;
  }
  oss << "------- Mapping from Item to <Index, Frequency> Pair ------\n";
  for (typename ItemHashMap::const_iterator i = item_map_->begin();
       i != item_map_->end();
       ++i) {
    oss << "INDEX " << i->second.value << " FREQUENCY "
        << i->second.frequency << " ITEM " << i->first
        << endl;
  }
  oss << "-----------------------------------------------------------\n";

  return oss.str();
}

}  // namespace frequent_pattern_mining

#endif  // FP_GROWTH_DICTIONARY_H_
